package main.Q401_500;

import java.util.*;

public class Q431_440 {
	public static void main(String[] args) {
		System.out.println("Question431：");
		System.out.println("Question432：");
		System.out.println("Question433：");
		System.out.println("Question434：字符串中的单词数");
		System.out.println("Question435：无重叠区间");
		System.out.println("Question436：寻找右区间");
		System.out.println("Question437：路径总和 III");
		System.out.println("Question438：找到字符串中所有字母异位词");
		System.out.println("Question439：");
		System.out.println("Question440：");
	}
}

class Question434 {
	public int countSegments(String s) {
		int count = 0;
		for (int i = 0; i < s.length(); i++) {
			if ((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ') {
				count++;
			}
		}
		return count;
	}
}

class Question435 {
	public int eraseOverlapIntervals(int[][] intervals) {
		int i = 0, j = 0;
		Arrays.sort(intervals, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[1] != o2[1]) return o1[1] - o2[1];
				else return o1[0] - o2[0];
			}
		});
		Deque<int[]> deque = new LinkedList<>();
		while (i < intervals.length) {
			int[] temp = intervals[i];
			for (j = i + 1; j < intervals.length; j++) {
				if (intervals[j][1] == temp[1]) temp = intervals[j];
				else break;
			}
			i = j;
			int[] last = deque.peekLast();
			if (last == null || last[1] <= temp[0]) deque.addLast(temp);
		}
		return intervals.length - deque.size();
	}
}

class Question436 {
	public int process2(int[][] temp, int index) {
		int left = index, right = temp.length - 1, result = Integer.MAX_VALUE;
		int end = temp[index][1];//当前结尾
		if (left != right) {
			while (left < right) {
				int mid = left + (right - left) / 2;
				if (temp[mid][0] >= end) {
					right = mid;
				} else left = mid + 1;
			}
			if (temp[left][0] >= end) result = temp[left][0];
		}
		return result;
	}

	public int process1(int[][] temp, int target) {//获取排序后目标区间的下标
		int index = 0, left = 0, right = temp.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (temp[mid][0] == target) {
				index = mid;
				break;
			} else if (temp[mid][0] >= target) right = mid - 1;
			else if (temp[mid][0] <= target) left = mid + 1;
		}
		return index;
	}

	public int[] findRightInterval(int[][] intervals) {
		int length = intervals.length, minIndex = -1;
		int[] result = new int[length];
		int[][] temp = new int[length][2];
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < length; i++) {
			map.put(intervals[i][0], i);//记录区间和下标的对应
			temp[i][0] = intervals[i][0];//生成排序数组
			temp[i][1] = intervals[i][1];
		}
		Arrays.sort(temp, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		for (int i = 0; i < length; i++) {
			int index = process1(temp, intervals[i][0]);//获取排序后的下标
			int minStart = process2(temp, index);//获取最小化的区间start
			minIndex = minStart == Integer.MAX_VALUE ? -1 : map.get(minStart);
			result[i] = minIndex;
		}
		return result;
	}
}

class Question437 {
	HashMap<Long, Integer> prefix;

	public int pathSum(TreeNode root, int targetSum) {
		prefix = new HashMap<>();
		prefix.put(0L, 1);
		return dfs(root, 0, targetSum);
	}

	public int dfs(TreeNode root, long curr, int targetSum) {
		if (root == null) return 0;
		int ret = 0;
		curr += root.val;
		ret = prefix.getOrDefault(curr - targetSum, 0);
		prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
		ret += dfs(root.left, curr, targetSum);
		ret += dfs(root.right, curr, targetSum);
		prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
		return ret;
	}
}

class Question438 {

	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> result=new ArrayList<>();
		if(s.length()<p.length()) {
			return result;
		}
		int[] target=new int[26];
		for(char c:p.toCharArray()) {
			target[c-'a']++;
		}
		int[] orig=new int[26];
		char[] arr=s.toCharArray();
		for(int i=0;i<p.length();i++) {
			orig[arr[i]-'a']++;
		}
		int left=0,right=p.length()-1;
		while(right<arr.length) {
			if(process(target,orig)) {
				result.add(left);
			}
			orig[arr[left]-'a']--;
			left++;
			right++;
			if(right<arr.length) {
				orig[arr[right]-'a']++;
			}
		}
		return result;
	}

	public boolean process(int[] target,int[] orig) {
		for(int i=0;i<target.length;i++) {
			if(target[i]!=orig[i]) {
				return false;
			}
		}
		return true;
	}

//	public boolean process(Map<Character, Integer> sMap, Map<Character, Integer> pMap) {
//		for (Character key : pMap.keySet()) {
//			if (!sMap.containsKey(key) || sMap.get(key) != pMap.get(key))//若不存在或存在不相等
//				return false;
//		}
//		return true;
//	}
//
//	public List<Integer> findAnagrams(String s, String p) {
//		int sLen = s.length(), pLen = p.length();
//		if (sLen < pLen) return new ArrayList<Integer>();
//		List<Integer> ans = new ArrayList<Integer>();
//		int[] count = new int[26];
//		for (int i = 0; i < pLen; ++i) {
//			++count[s.charAt(i) - 'a'];
//			--count[p.charAt(i) - 'a'];
//		}
//		int differ = 0;
//		for (int j = 0; j < 26; ++j) {
//			if (count[j] != 0) ++differ;
//		}
//		if (differ == 0) ans.add(0);
//		for (int i = 0; i < sLen - pLen; ++i) {
//			if (count[s.charAt(i) - 'a'] == 1) --differ;// 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
//			else if (count[s.charAt(i) - 'a'] == 0) ++differ;// 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
//			--count[s.charAt(i) - 'a'];
//			if (count[s.charAt(i + pLen) - 'a'] == -1) --differ;// 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
//			else if (count[s.charAt(i + pLen) - 'a'] == 0) ++differ;// 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
//			++count[s.charAt(i + pLen) - 'a'];
//			if (differ == 0) ans.add(i + 1);
//		}
//		return ans;
//	}
}